package ztttt1;

import java.util.*;

public class Test3 extends MyList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);


    }
    //141.环形链表
    public class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null){
                return false;
            }
            ListNode slow = head;
            ListNode fast = head;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    return true;
                }
            }
            return false;
        }
    }

    //160.相交链表
    public class Solution1 {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode curA = headA;
            ListNode curB = headB;
            int num1 = 0;
            int num2 = 0;
            int len = 0;
            while(curA != null){
                num1++;
                curA = curA.next;
            }
            while(curB != null){
                num2++;
                curB = curB.next;
            }
            if(num1 > num2){
                len = num1 - num2;
                for(int i = 0;i < len;i++){
                    headA = headA.next;
                }
            }else if(num1 <= num2){
                len = num2 - num1;
                for(int i = 0;i < len;i++){
                    headB = headB.next;
                }
            }
            while(headA != headB){
                headA = headA.next;
                headB = headB.next;
            }
            return headA;
        }
    }
    //链表分割
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            ListNode listMin = new ListNode();
            ListNode listMax = new ListNode();
            ListNode min = listMin;
            ListNode max = listMax;
            ListNode node = pHead;
            while(node != null){
                if(node.val <= x){
                    listMin.next = node;
                    listMin = listMin.next;
                }else if(node. val > x){
                    listMax.next = node;
                    listMax = listMax.next;
                }
                node = node.next;
            }
            while(max != null){
                listMin.next = max;
                max = max.next;
                listMin = listMin.next;
            }
            return min;
        }
    }
    //链表的回文结构
    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            if(A == null){
                return false;
            }
            if(A.next == null){
                return true;
            }
            ListNode slow = A;
            ListNode fast = A;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode node = slow.next;
            while(node != null){
                ListNode nodenext = node.next;
                node.next = slow;
                slow = node;
                node = nodenext;
            }
            while(A != slow){
                if(A.val != slow.val){
                    return false;
                }
                if(A.next == slow){
                    return true;
                }
                A = A.next;
                slow = slow.next;
            }
            return true;
        }
    }
}







